﻿// array_range_sum.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <sstream>
using namespace std;


/**
 * 计算数组的S值
 * 将数组按每3个元素分组，每组去掉最大值和最小值，保留中间值
 * 所有中间值的和就是S值
 */
int calculateSValue(const vector<int>& arr) {
    int totalS = 0;
    // 按每3个元素进行分组处理
    for (int i = 0; i < arr.size(); i += 3) {
        // 提取当前三元组并排序，取中间值
        vector<int> triplet = { arr[i], arr[i + 1], arr[i + 2] };
        sort(triplet.begin(), triplet.end());
        totalS += triplet[1]; // 累加中间值
    }
    return totalS;
}

/**
 * 生成当前数组状态下所有可能的一步移动结果
 * 一步移动定义为：取出一个元素，插入到另一个位置
 */
vector<vector<int>> getAllOneMoves(const vector<int>& arr) {
    vector<vector<int>> moves;
    int n = arr.size();

    // 遍历每个可以移动的元素位置
    for (int i = 0; i < n; i++) {
        int element = arr[i]; // 要移动的元素
        cout << "current element: " << element << endl;
        // 创建移除该元素后的临时数组
        vector<int> tempArr;
        for (int k = 0; k < n; k++) {
            if (k != i) tempArr.push_back(arr[k]);
        }

        // 尝试将该元素插入到每个可能的位置
        for (int j = 0; j <= tempArr.size(); j++) {
            // 构造插入元素后的新数组
            vector<int> newArr = tempArr;
            newArr.insert(newArr.begin() + j, element);
            // 只保留真正改变了状态的数组
            if (newArr != arr) {
                moves.push_back(newArr);
            }
        }
    }
    return moves;
}
/*
*主求解函数
* 使用BFS（广度优先搜索）找到达到最大S值所需的最少移动次数
* */
void solve() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    /*
    vector<int> arr;  // [1 2 3]
    int num;
    while (iss >> num) {
        arr.push_back(num);
    }*/
    vector<int>arr{ 1, 2, 3, 4, 5, 6 };
    int n = arr.size(); //3

    // 计算理论最大S值(等差数列推理)
    int sMax = (2 * n * n) / 9;

    // 初始化BFS队列和访问集合
    queue<pair<vector<int>, int>> q;
    q.push({ arr, 0 }); // {[1,2,3], 0}
    set<vector<int>> visited;
    visited.insert(arr); // {[1,2,3]}

    // BFS主循环
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        vector<int> currentArr = current.first; //[1,2,3]
        int moves = current.second; //0

        cout << "moves: " << moves << endl;

        // 检查当前状态是否达到最大S值
        if (calculateSValue(currentArr) == sMax) {
            cout << moves << endl; // 输出最少移动次数
            return;
        }

        // 如果还没有超过最大搜索深度，继续扩展搜索
        if (moves < n) {
            // 获取当前状态的所有一步移动结果
            for (const auto& nextState : getAllOneMoves(currentArr)) {
                // 如果这个状态没有被访问过
                if (visited.find(nextState) == visited.end()) {
                    visited.insert(nextState); // 标记为已访问
                    q.push({ nextState, moves + 1 }); // 加入队列
                }
            }
        }
    }

    // 如果在n步内找不到解决方案，输出n作为默认值
    cout << n << endl;
}

int main()
{
    /*vector<int>num_vec;
    string input;
    getline(cin, input);
    stringstream sstream(input);

    string num_str;
    while (sstream >> num_str)
    {
        num_vec.push_back(stoi(num_str));
    }*/
    solve();
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
